package Hash表.赎金信_383;

/*
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：
1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成

思路：
        很典型的hash表，相较于有效的字母异位词区别在于，b包含a即可，无需互相包含
        1. 用数组模拟hash表记录b中的每个字符出现的次数（转换为数字）
        2. 在hash表中减去用a中出现的字符的次数
        3. 遍历数组出现负数则说明b中不包含

时间复杂度: O(n+m)
空间复杂度: O(n)

* */
public class Solution {
    public static void main(String[] args) {
        String ransomNote = "aa", magazine = "aab";
        System.out.println(canConstruct(ransomNote, magazine));
    }
    public static boolean canConstruct(String ransomNote, String magazine) {
        // 定义只有26个数字的hash表
        int[] str = new int[26];
        for (int i = 0; i < magazine.length(); i ++){
                str[magazine.charAt(i) - 'a'] ++;
            }
        for (int i = 0; i < ransomNote.length(); i ++){
            str[ransomNote.charAt(i) - 'a'] --;
        }
        for (int i = 0; i < 26; i ++){
            if (str[i] < 0){
                return false;
            }
        }
            return true;
    }
}
